package com.LeetCode.dp;

import org.junit.Test;

/**
 * 数字三角
 */
public class MathTriangle {


    int[][] matrix;

    int[][] dp;

    int res, n, m;

    public int findMaxPath(int[][] matrix){
        this.matrix = matrix;
        this.n = matrix.length;
        this.m = matrix[0].length;
        dp = new int[n][m];
        return dfs(0,0);
    }

    public int dfs(int i, int j){
        if(i >= n || j >= m){
            return 0;
        }

        if(dp[i][j] != 0)
            return dp[i][j];

        dp[i][j] = Math.max(dfs(i+1, j) , dfs(i+1, j+1)) + matrix[i][j];

        return dp[i][j];
    }

    @Test
    public void test(){
        int[][] matrix = {
                {7,0,0,0,0},
                {3,8,0,0,0},
                {8,1,0,0,0},
                {2,7,4,4,0},
                {4,5,2,6,5}
        };
        System.out.println(findMaxPath(matrix));
    }
}
